%\documentclass{cccg11} 
\documentclass{article}

\usepackage{amsmath}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
%\usepackage{url, color, epsfig, amsmath, amsthm, amssymb}
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
\input mac
\def\F{\ensuremath{\mathcal{F}}}
\def\H{\ensuremath{\mathcal{H}}}
\def\R{\ensuremath{\mathcal{R}}}
\def\C{\ensuremath{\mathcal{C}}}
\def\eps{\ensuremath{\epsilon}}
\def\conv{\ensuremath{conv}}
%\newcommand{\remove}[1]{}
\def\polylog{{\mathop{\mathrm{polylog}}\nolimits}}
%\newtheorem{corollary}[theorem]{Corollary}

\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
%\newtheorem{observation}{Observation}
%\newtheorem{defi}{Definition}
%\newtheorem{speculation}{Speculation}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\inprod}[2]{\left\langle #1 , #2 \right\rangle}
%\newsavebox{\smallProofsym}                            
% smallproofsymbol
%\savebox{\smallProofsym}                               %
%\begin{picture}(6,6)                                   %
%\put(0,0){\framebox(6,6){}}                            %
%\put(0,2){\framebox(4,4){}}                            %
%\end{picture}                                          %
%            \fi\fi}
%}   

%----------------------- Macros and Definitions
%--------------------------

% Add all additional macros here, do NOT include any additional files.

% The environments theorem (Theorem), invar (Invariant), lemma
% (Lemma),
% cor (Corollary), obs (Observation), conj (Conjecture), and prop
% (Proposition) are already defined in the cccg08.cls file.
% Add additional environments only if you REALLY need them.

%\newcommand{\qed}{\vrule height8pt width8pt depth4pt}
\def\qedbox{\vrule width 0.61em depth 0.12em height 0.49em}
\def\qed {\ifinner \noalign {\global\dimen1=\prevdepth
\ifdim\prevdepth=-1000pt \global\dimen1=0pt \fi
\vskip-\dimen1 \nointerlineskip}
\omit\span\omit \hfil
\vbox to -\dimen1{\vss
    \hbox to 0pt{\hss \hbox to \hsize{\hfill\qedbox}\hss}}\hfil\crcr
 funktionirt auch in \eqalign (nach dem letzten \cr)
\else \ifmmode \eqno\qedbox
       \else \qquad\hbox{}\nobreak\hfill \nopagebreak \qedbox\par \smallskip
            \fi\fi}
%----------------------- Title
%-------------------------------------------

\title{Ray-Shooting Depth in $\reals^2$- Algorithms and Applications}

\author{ Mudassir Shabbir\footnote{Department of Computer Science, Rutgers
University, 110 Frelinghuysen Road, Piscataway, New Jersey
08854-8004; {\tt (mudassir@cs.rutgers.edu.)}}  }

\index{Shabbir, Mudassir}

\begin{document}
\thispagestyle{empty}

\maketitle
\begin{abstract}
The notion of \emph{Ray Shooting Depth} was introduced in recent papers
of Gromov, and of Fox, Gromov, Lafforgue,  Naor, and Pach. It played a
key role in their results. It also represents a new concept for data depth in
$\reals^d$ and offers interesting possibilities for applications. Here, we
study some computational aspects of ray-shooting depth in dimension
two via algorithms and some complexity results. In addition we
advocate the use of ray-shooting depth in statistical data
analysis and in other applications. We illustrate some of the
desireable properties via comparisons with other notions of depth.
\end{abstract} 

\bigskip

\section{Introduction}

\label{sec:intro}

\bigskip
 Given a set $S=\{P_1,\ldots,P_n\}$ of $n$ points in general position
in $\reals^2$ (the data) $G=(V,E)$ denotes the complete geometric graph
whose vertices are the points of $S$ and edges, the segments
$\overline{P_iP_j}, i<j$.  

For a point $Q\in \reals^2$, the {\em ray-shooting depth of $Q$} is defined as 
\begin{equation}
d_{\rho}(Q)=\min_{u:\|u\|=1}(r(Q,u)),
\end{equation}
where  $r(Q,u)$ is the number of segments in $E$  that meet 
$\{Q+tu, t \geq 0\}$, the ray through $Q$ in direction $u$. A
(ray-shooting) median is a point $\mu_{\rho}\in \reals^2$ of maximal
ray-shooting depth. It need not be unique nor an element of $S$.

Ray shooting depth is the specialization to two dimensions of a notion that
was proposed in recent papers of Gromov \cite{kn:gromov} and Fox
et.al. \cite{kn:fox}. In \cite{kn:fox} it was instrumental in
establishing a new lower bound for the maximal number of $d-$simplices
that are defined by $n$ points in general position in $\reals^d$, and which
have non-empty intersection. The notion has other important combinatorial
consequences as well. 

In the present paper we focus on the two dimensional version and
recommend adding it to the set of concepts used to define data
depth in terms of a set $S$ of $n$ given points in $\reals^2$. For this
purpose it is necessary to understand the computational properties. 

 We give a simple algorithm, along with a matching lower bound to show that

\begin{theorem}

\label{thm1}

Given a set $S$ of $n$ points in $\reals^2$and a query point $Q$, $d_{\rho}(Q)$
can be computed in time $\Theta(n\log{n})$.

\end{theorem}
In addition we show that
\begin{theorem}

\label{thm2}
Given a set $S$ of $n$ points in $\reals^2$, a median $\mu_{\rho}\in \reals^2$ and its
depth $d_{\rho}(\mu_{\rho})$ can be found in $O(n^4)$.

\end{theorem}
We dont know a lower bound better than that given by Theorem 1.
Because of this gap, the following result may be useful.
\begin{theorem}

\label{thm3}

Given a set $S$, of $n$ points in $\reals^2$, we can compute $d_{\rho}(P_i),
i=1,\ldots,n$ in $O(n^2)$ time. In addition, in $O(n\log^2 n)$ time, we can
find a point $Q\in \reals^2$ with $d_{\rho}(Q)\geq d_{\rho}(P_i)$, $i=1,\ldots,n$.

\end{theorem}

The algorithms are described in the next section, along with the
arguments for the asserted complexities.  The remaining sections of the paper
are offered in support of our endorsement of ray-shooting depth for
data analysis and other applications. 

In Section 3 we compare ray shooting depth to four known data depth
measures that have some currency in application. Each of them defines
the  depth of a point $Q \in \reals^d$ based on a given  set $S$ of $n$ points
in general position in $\reals^d$, though we will only be considering the $d=2$ versions. These
depth notions  are:
\begin{itemize}
\item {\bf Tukey depth $d_{\tau}$:} Defined by John Tukey \cite{kn:tukey}
and sometimes called the halfspace depth of a point $Q\in R^d$, it is defined as
\begin{equation}
d_{\tau}(Q)=\min_{u:\|u\|=1}(h_{min}(Q,u)),
\end{equation}
where  $h_{min}(Q,u)$ denotes the minimum of the numbers of points of $S$ in the
the two closed halfspaces determined by the hyperplane through
$Q$ with normal vector $u$. A Tukey median is a point $\mu_{\tau}\in
R^d$ of maximal Tukey depth. It need not be unique nor an element of $S$. It is known
that $d_{\tau}(\mu_{\tau})\geq \lfloor n/(d+1) \rfloor$, a simple
consequence of Helly's theorem. 
\item {\bf  Simplicial depth $d_\sigma$:} First proposed by Regina Liu
\cite{kn:liu}, it is defined by
\begin{equation}
d_{\sigma}(Q)=\sum_{\Delta \in {S\choose d+1}}I_{Q\in \Delta}
\end{equation}
where ${S\choose d+1}$ denotes the set of $d-$simplices with vertices
in $S$ and $I$, the indicator function. A simplicial median is a point
$\mu_{\sigma}\in \reals^d$ of maximal simplicial depth. It need not be
unique nor an element of $S$. It is known that
$d_{\sigma}(\mu_{\sigma})\geq c_d{n\choose d+1}$; i.e., for every set
$S$, there is a point in a fixed fraction of all simplices. Boros and
Furedi proved that $c_2=2/9$ and B\'{a}r\'{a}ny showed $c_d\geq
(d+1)^{-d}$, a lower bound recently improved by Gromov
\cite{kn:gromov} to $2d/[d!(d+1)^2]$, exponentially larger than
B\'{a}r\'{a}ny\'s bound.
\item {\bf Oja Depth} It is defined by
\begin{equation}
d_{\sigma}(Q)=\sum_{\Delta \in {S\choose d}}\mbox{VOL}(Q\Delta)
\end{equation}
the sum of the volumes of all $d-$simplices having $Q$ as a vertex,l
 along with $d$ points of $S$.
\end{itemize}
%need a smmoother intrgration here
-----------

We follow these theoretical results with simple and easily portable 
implementations. Particularly we discuss $RSplot$, a new bivariate
data visualization tool that we developed based on Ray Shooting
algorithms. Software we developed are open source and freely available
in R, the standarad statistical development environment. 

We also conducted an experimental study to compare accuracy and
robustness of RS depth with already known data depth measures Tukey,
Simplicial, Oja, and Spatial medians on relatively large data sets
chosen randomly from eleven different distributions. We discuss
details of our method and results for this simulation in the last
section.

\section{Algorithms}

\label{sec:algos}
For the discussion below, we abuse following notations : $(a,
b)$ to mean a line passing through, and $[a, b]$ to mean a line
segment through points $a, b$ and $[a, b)$ to mean a half infinite ray starting at $a$ and
passing through $b$. Also for a point $p\in \reals^2$, its dual line is
denoted by $p^*$; we do not fix any point line duality, and any
definition that preserves incidence and above/below relationship will
suffice.

\subsection{RS Depth of one point}
To find ray shooting depth of a point $Q_i$ in some direction $r$, it helps to assume
that all points $P_j$ lie on a unit circle with $Q_i$ as its center. Reader should note that 
this assumption is available without loss of generality. Now we sort all $P_j$ radially around 
$Q_i$, and let $P_0, P_1,P_2...P_n$ be the clockwise ordering, where $(Q_i,P_0)$ is the direction $r$ and
 let $-P_1,-P_2...-P_n$ be the respective antipodal points on circle. We observe that all edges $[P_1,P_k]$
intersect $r$ for all $P_k$, s.t. radial order of $P_k$ is greater than $-P_1$. In general, 
$\rho_{i,1}\gets \sum_{k=1}^n(n-arc_{i,k}-k-1)$ is the number of all edges intersecting a ray in direction 
direction of $P_1$, where $arc_{i,j} $ is the number of points as we walk clockwise from some point 
$P_{j}$ to $-P_{j}$. Once we know, $\rho_{i,1}$, ray shooting depth in direction of $P_1$, its easy to see the depth 
$\rho_{i,2}$ can be calculated in constant time using
$\rho_{i,r}\gets  (\rho_{i,r-1} - n + 2	\times arc_{i,j-1} + 1)$. Using this we calculate depth
 in all $n$ directions, and take the minimum as the depth of the point $Q_i$.
So the time complexity is dominated by the sorting. We show in section ??? that 
this is unfortunately unavoidable.


\subsection{RS Depth of a pointset}
--------------------------
Let $P=\{P_1\ldots,P_n\}$ and $Q=\{Q_1,\ldots,Q_m\}$ be sets of points
in $\reals^2$ of sizes $n$ and $m$, respectively.  we
give following algorithm to compute RS Depth, $\rho(P, Q_i), \forall
Q_i\in Q$.

\begin{algorithm}                      

\caption{RS Depth of $|Q|=m$ with respect to $|P|=n$}   

\label{alg1} 

\begin{algorithmic}[2]

\STATE build $\mathcal{A}(P)$, the arrangment of $p_i^*$ for $p_i\in
P$
\FORALL{$q_i \in Q$}
	\STATE $L_i\gets \{l_{i,j}:$ slope of $(q_i,p_j) \}$
	\STATE sort $L_i$ by inserting $q_i^*$ in
	$\mathcal{A}(P)$. W.L.O.G. $l_{i,1}\leq l_{i,2}\ldots \leq
	l_{i,n}$ be in anti-clockwise order on unit circle with $q_i$
	as center. Also $p_{i,j}\in P$ be alias of a point with which
	makes slope $l_{i,j}$ with $q_i$.
\ENDFOR
\STATE \textbf{end for}
\FORALL{$q_i \in Q$}
	\STATE $arc_{i,j}\gets $ number of points as we walk clockwise from
	$p_{i,j}$ to $-p_{i,j}$.
	\STATE $\rho_{i,1}\gets \sum_{k=1}^n(n-arc_{i,k}-k-1)$	

	\FOR{$r = 2 \to n$}

			\STATE $\rho_{i,r}\gets  (\rho_{i,r-1} - n + 2
			\times arc_{i,j-1}+1)$			

	\ENDFOR

	\STATE \textbf{end for}

	\STATE $\rho_i \gets \min_{j=1}^n \rho_{i,j}$

\ENDFOR

\STATE \textbf{end for}

 $\rho$

\end{algorithmic}

\end{algorithm}  

We essentially repeat the first algorithm for all points in $Q$, except for one little trick: 
we will need the sorted order of all $P_i$ with respect to all $Q_j$, but instead of applying
the sorting algorithm for all $Q_i$, we build an arrangement of dual lines of $P \cup Q$, get 
the required slopes in sorted order in $O((n+m)^2)$ using Edelsbrunners algorithm. $O(n^2+m^2)$ complexity
 of the rest of the algorithm is obvious.

\subsection{Algorithm to compute RS-Median of a Pointset}

Given a set $P$ of $n$ points in plane, we give an algorithm to
compute RS-Depth of all, \emph{combinatorial}, points in plane, also locate an arbitrary
point $z$ such that $\delta(z)\geq \delta(z\prime), \forall
z\prime\in\reals^2 $. 

We divide plane into a set of faces defined by the arrangemnt
$\mathcal{A}(E_P)$, of $ {n\choose 2}$ lines induced on points in
$P$. We observe that all points within a face have same RS-Depth, and
also we note a relation between $\delta$ values of $delta$ values of
points in neighboring faces. We define $N(f_i, P)$ as set

of all neighbor faces of face $f_i$ where two faces are neighbors to
each other if they share a common edge. $N(f_i) = N(f_i, P)$ where $P$
is obvious from the context. We fix $f_0$ to be the unbounded face of
this arrangment which is rather a union of all unbounded faces but we
will use it just one face whose description is readily available by
taking the convex hull of $P$. Algorithm follows:

\begin{algorithm}                      

\caption{RS Median of a set $|P|=n$}   

\label{alg2} 

\begin{algorithmic}[2]

\STATE build $\mathcal{A}(E_P)$, the arrangment of $(p_i,p_j)\in
P\times P$

\STATE Let $F=$ set of all faces in $\mathcal{A}(E_P)$.

\FORALL{$f_i \in F$}

	\STATE $label(f_i)\gets \infty$

\ENDFOR

\STATE \textbf{end for}

\STATE $count \gets 0$

\STATE $label(f_i)\gets count$

\STATE $L \gets \{f_i\} $

\STATE $S\gets L$

\REPEAT

\STATE $R\gets S$

\STATE $S\gets \emptyset$

\STATE $count \gets count +1 $

\FORALL{$l_i \in L$}

	\STATE Remove $l_i$ from $L$

	\FORALL{$f_j \in N(l_i), s.t. label(f_j) = \infty $}

		\STATE $label(f_j) \gets count $

		\STATE $S\gets S\cup \{f_j\}$		
	\ENDFOR

	\STATE \textbf{end for}
\ENDFOR
\STATE \textbf{end for}
\STATE $L \gets S $

\UNTIL{ $L = \emptyset$ }

RETURN $R$ as set of RS-Median points.

\end{algorithmic}

\end{algorithm}  

\begin{lemma}

For any two points $x,y$ in some $f_i$, $\delta(x)=\delta(y)$ always
holds.

\end{lemma}

\begin{lemma}

Finding neighbors takes const time.

\end{lemma}


\subsection{Lower bound on computing RS-Depth of a point}

In this section we prove $\Omega(n log n)$ lower bound on algorithm
computing RS-Depth of a query point $q$ for a n-pointset $P \in \reals^2$
in algebraic computation tree model. We provide a linear time
reduction from set-equality problem: Given two sets $A =
\{x_1,x_2,\ldots,x_n\}$ and $B = \{y_1,y_2,\ldots,y_n\}$ in $R$, it
takes $\Omega(n log n)$ computations to decide whether or not $A = B$.

\begin{lemma}
Any algebraic computation tree that solves $n$-points RS-Depth problem
 has a complexity $\Omega(n log n)$
\end{lemma}

\noindent
{\bf Proof:} 
Given two sets $A = \{x_1,x_2,\ldots,x_n\}$ and $B =
\{y_1,y_2,\ldots,y_n\}$ we construct $P \in \reals^2$, such that by
finding out depth of origin $w.r.t P$ we will be able to decide
$A=B?$. First, without loss of generality we assume that
$0<x_i<\frac{\pi}{2}, \forall x_i\in A$, if not we know that a mapping
always exists. Similarly $0<y_i<\frac{\pi}{2}, \forall y_i\in B$. Now
for each $x_i\in A$ we define $p_i=(\frac{i}{n},cos(x_i))$, and for
each $y_j\in B$, $p_{n+j}=(-\frac{j}{n},cos(y_j+\frac{\pi}{2}))$. We
claim.
\begin{claim}

\label{claim1}

If $\delta(O)=\frac{n^2}{8}$ for set $P=\{p_1,p_2,\ldots,p_{2n}\}$,
where $O=(0,0)$, then $A=B$.

\end{claim}

\noindent
{\bf Proof:}
Let us suppose otherwise that $A \neq B$, and W.L.O.G. $x_1\leq
x_2\ldots \leq x_n$ and $y_1\leq y_2\ldots \leq y_n$ and let $i$ be
smallest such that $x_i<y_i$. By our construction it implies that
$p_i\neq p_{n+i}$. Now consider the line $l$ passing through $O$ such
that both 

 Consider the line passing through $O$ s.t. both $p_i, p_{n+i}$ lie to
 the right of it and points $p_{i+1},p_{i+2}\ldots,p_{n}$ are on
 left. We see that $(\frac{n}{2}-1).(\frac{n}{2}+1)$ line segments
 induced on $P$ intersect this line, hence at least one of the two
 rays in $l$ starting at $O$ intersects at most $\frac{n^2}{8}-1$ line
 segments contradicting the assumption that $\delta(O)=\frac{n^2}{8}$.
\qed

%\begin{figure}[!h]
 %   \begin{center}
%        \scalebox{0.45}{
%            \includegraphics[scale=0.75,bb=400 600 385 567]{lb3.pdf}}
%    \end{center}
%            \caption{\small Aweome picture!}
%            \label{tree}
%\end{figure}

\begin{claim}

\label{claim2}

If $\delta(O)<\frac{n^2}{8}$ for set $P=\{p_1,p_2,\ldots,p_{2n}\}$,
where $O=(0,0)$, then $A\neq B$.

\end{claim}

\noindent
{\bf proof}

Again assume $A=B$. By construction of $P$, we note that for any
$p_i\in P$, there is exactly one antipodal point $p_j\in
P$. Furthermore any line $l$ passing through $O$ is a halving line of
$P$: both half-planes such defined have exactly $\frac{n}{2}$ points
(unless $l$ passes through some $p_i$ which we discuss later). So
$\frac{n^2}{4}$ line segments intersect each line, and as points are
arranged symmetrically around $O$ in first and third quadrants of
plane, both half infinite rays of such $l$ starting at $O$ intersect
equal number of line segments.

In case of a line passing through two antipodal points in $P$, line
intersects $(\frac{n}{2}-1)^2.(n-1)$ segments and each ray intersects
at least $\frac{n^2}{8}+\frac{n-1}{2}$ line segments. This contradicts
the assumption that $\delta(O)<\frac{n^2}{8}$ implying $A\neq B$.\qed

Claim~\ref{claim1} and Claim~\ref{claim2} complete the reduction by
showing that computing RS Depth of set of $n$ points in plane, we can
decide set equality. Lower bound follows.\qed

\section{RSplot: A Bivaruate Data Visulization Tool}

Given remarkable accuracy of Ray Shooting depth to rank points in plane, as observed in Simulations section below, 
its natural to consider it for purpose of bivariate data representation and outlier identification.
We present RSplot, a variant of Bagplot, using Ray
Shooting depth instead of Tukey depth. Main components of RSplot
include:

\begin{itemize}
	\item RS median point: a point of maximum RS depth.
	\item Median bag: convex hull of set of all median points. 
	\item Half bag: a convex polygon that contains 50\% points in
	$P$.
	\item Fence: a polygon that identifies outliers in data.
\end{itemize}

%\onecolumn
\begin{figure*}
        \scalebox{0.26}{            
            %includegraphics[width=400pt, height=400pt]{pdfs/norm_rings.pdf}
						\includegraphics{pdfs/norm_rings.pdf}
	    %includegraphics[width=400pt, height=400pt]{pdfs/exp_rings.pdf}
			\includegraphics{pdfs/exp_rings.pdf}
            %includegraphics[width=400pt, height=400pt]{pdfs/unif_rings.pdf}
						\includegraphics{pdfs/unif_rings.pdf}
	}
\caption{Five rings of RS depth for sets of $500$ points at random, respectively, from norm bivariate, exponential bivariate and uniform bivariate distributions.}
            \label{tree}
\end{figure*}
\begin{figure*}
        \scalebox{0.26}{            
            %\includegraphics[width=400pt, height=400pt]{pdfs/norm_trings.pdf}
	    %\includegraphics[width=400pt, height=400pt]{pdfs/exp_trings.pdf}
       %    \includegraphics[width=400pt, height=400pt]{pdfs/unif_trings.pdf}
			
			    \includegraphics{pdfs/norm_trings.pdf}
	    \includegraphics{pdfs/exp_trings.pdf}
          \includegraphics{pdfs/unif_trings.pdf}
	}
	\caption{Five rings of RS depth for sets of $50$ points at random, respectively, from normal bivariate, exponential bivariate and uniform bivariate distributions.}
            \label{tree2}
\end{figure*}
\begin{figure*}
        \scalebox{0.40}{            

            %\includegraphics[scale=0.75,bb=0 0 300 567]{pdfs/rsplotdh1.pdf}
				
				%\includegraphics[width=500pt, height=500pt]{pdfs/rsplotdh1.pdf}
				%\includegraphics[width=500pt, height=500pt]{pdfs/rsplottc1.pdf}
				\includegraphics{pdfs/rsplotdh1.pdf}
				\includegraphics{pdfs/rsplottc1.pdf}
	    %\
				
	    %\includegraphics[scale=0.75,bb=800 0 700 567]{pdfs/rsplottc1.pdf}
            %\includegraphics[scale=0.75,bb=1150 0 385 567]{pdfs/unif_rings.pdf}
	}
\caption{(left)}
\label{tree3}
\end{figure*}
We implemented RSplot, in R, the standard statistical computing
language so that it is readily available to use and extend on all
recognised palteforms. As we also provide its source in C++, it can
easily be ported to other environment. R package for current
implementation is available on all R CRAN servers and link to main
repositorty is \emph{http://cran.r-project.org/web/packages/rsdepth/}. Some examples
where RSplot is used to represent some real world data follow: 
%TODO reference to the figure

%TODO: add reference for the data


\section{Simulations}

\label{section:simulations}


\subsection{Results}

Results of our experiments follow in ten tables at the end of this
section, one for each distribution used as source of data set; two
rows in each table represent tested median approximator's value for
$RMSE$ and $Bias^2$. Our interpretation of these results follow:

Ray Shooting or RS depth behaved well against all pure distributions
beating Tukey and Simplicial estimators in both error value and $bias$
in many cases and remaining close by in rest of them. $Bias$ value of
RS-Depth in case of 10\% (and 30\% as well) contamination of Normal by
displaced mean Normal was higher than other estimators. We observe
that in rest of the cases $bias$ and error values were not that
bad. This performance of Ray Shooting depth on contaminated data sets
shows that empirically RS Depth is more robust than Tukey Depth;
difference is clearly discernible in Table~\ref{table:2}.

Tukey median is extremely low error for all pure distributions except
perhaps Uniform distribution, for which, all estimators that are based
on random process for selecting a median, are expected to show some
error. For contaminated distributions, performance of Tukey median was
bit worse, specially in case when Cauchy distribution is contaminated
with 30\% Normal, estimates  by Tukey median are observed to be
significantly worse than all other candidate medians.

Simplicial median started poorly with extremely high $bias^2$ (170+)
for Normal distribution, didn't do much well for F distribution
either. Performance on contaminated data sets was, comparatively
better being a clear winner in case of Cauchy distribution
contaminated with 30\% Normal, but error and bias in case Normal
distribution contaminated with 30\% Normal, is almost unacceptable.

Oja Depth behave very well in most of the cases on both bias value and
error term. At a couple of occasion in contaminated distributions, Oja
Depth was beaten by a nicer valued Liu/Simplicial Depth.

Spatial median is the only in our experiments for which we had an
efficient deterministic implementation to approximate center. And
expectedly, it outperforms rest of the candidates with respect to
accuracy and robustness in all distributions, as is clear from very
small values of error and bias.

 Need for efficient and easy to implement median algorithms for such
 data depth measures can't be overemphasized as current implementation
 of all these medians fall short against any sufficiently large
 data. Yet using RS-depth measure on a randomly chosen sample set to
 approximate is shown to be promising estimator for bivariate data
 sets.

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 0.01212 & 0.01213   & 12.542  & 0.01206 & 0.00100
\\ 

$Bias^2$ & 0.00031 & 0.00030 & 170.80 & 0.00030 & 0.00001
\\ 

   \hline

\label{table:1}

\end{tabular}

\caption{Normal Distribution}
\end{center}
\end{table}

\begin{table}[h]

\label{table:2}

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$   & 0.51137 & 0.51038 & 6.2419  & 0.51109 & 0.4999\\ 

  $Bias^2$ & 0.591 & 0.28396 & 51.173 & 0.28071 &  0.25038 \\ 

   \hline

\end{tabular}

\caption{Uniform Distribution}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$   & 0.03497 & 0.03547 & 0.68259 & 0.03832 & 0.00257
\\ 

  $Bias^2$ & 0.00287 & 0.00221 & 0.63617 & 0.00426 & 0.00001
  \\ 

   \hline

\end{tabular}

\caption{Cauchy Distribution}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 0.03517 & 0.03474 & 17.264 & 0.03625 & 0.00336 \\ 

  $Bias^2$ & 0.002 & 0.0026333 & 398.846 & 0.00268 & 0.00001
  \\ 

   \hline

\end{tabular}

\caption{F Distribution}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 0.03314   & 0.03389 & 0.66620 & 0.03307 & 0.00155
\\ 

  $Bias^2$ & 0.00228 & 0.00193 & 0.67679 & 0.00220 & 0.00001
  \\ 

   \hline

\end{tabular}

\caption{t Student Distribution}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 0.04925 & 0.04919 & 47.217 & 0.04909 & 0.00793 \\ 

  $Bias^2$ & 0.00480 & 0.00555 & 3569.0 & 0.00465 &  0.00008 \\ 

   \hline

\end{tabular}

\caption{Normal Distribution contaminated with 5\% Normal}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 1.30199 & 1.32381 & 0.68704 & 1.3495 & 1.2893 \\ 

  $Bias^2$ & 6.6741 & 1.7770 & 0.68264 & 1.90427 & 1.6708  \\ 

   \hline

\end{tabular}

\caption{Normal Distribution contaminated with 10\% Normal}

\end{center}

\end{table}



\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 1.2144 & 0.8427 & 42.408 & 0.98836 & 0.51845 \\ 

  $Bias^2$ & 2.6980 & 0.74255 & 3133.43 & 1.01717 &  0.26941 \\ 

   \hline

\end{tabular}

\caption{Normal Distribution contaminated with 30\% Normal}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 0.06544 & 0.06153 & 0.67546 & 0.06178 & 0.02044 \\ 

  $Bias^2$ & 0.00959 & 0.00699 & 0.67158 & 0.00815 & 0.00052  \\ 

   \hline

\end{tabular}

\caption{Cauchy Distribution contaminated with 5\% Normal}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

%\begin{tabular}{p{0.8cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}p{1.0cm}}
\begin{tabular}{rrrrrr}
  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 0.13426 & 0.13440 & 0.67908 & 0.12152 & 0.08139 \\ 

  $Bias^2$ & 0.03491 & 0.02599 & 0.62325 & 0.02810 & 0.00695  \\ 

   \hline

\end{tabular}

\caption{Cauchy Distribution contaminated with 10\% Normal}

\end{center}

\end{table}

\begin{table}[h]

\begin{center}

\begin{tabular}{rrrrrr}

  \hline

 & rs & tukey & liu & oja & spatial \\ 

  \hline

$RMSE$ & 2.93678 & 3.6032 & 0.68649 & 1.5975 & 1.6688 \\ 

  $Bias^2$ & 3.4831 & 13.0535 & 0.6657 & 2.7039 &  2.8049 \\ 

   \hline

\end{tabular}

\caption{Cauchy Distribution contaminated with 30\% Normal}

\end{center}

\end{table}

\bibliographystyle{alpha}	% (uses file "plain.bst")
\bibliography{r2_bill1}	
\end{document}

